package leetcode_1000;

/**
 * @author 周杨
 * 2018年11月19日 上午12:32:41 给定N首不同的歌 要求返回一个长度为L的列表 里面K首歌才能重复 要求每首歌放一遍
 * NumberOfMusicPlaylists_920.java
 * description:dp[i][j] = dp[i-1][j-1]*(N-(j-1))// 第i首歌不是前(j-1)首歌中的某一首歌

            + dp[i-1][j]*(j-K)  // 第i首歌是前j首歌中的某一首歌，与第(i-K):(i-1)首歌不同
            动态规划 AC 7%
 */
public class NumberOfMusicPlaylists_920 {
	public int numMusicPlaylists(int N, int L, int K) {
			final int MOD=1000000007;
			long dp[][]=new long[L+1][N+1];//dp[i][j]表示前i个列表 用J个music去填充的方法
			dp[0][0]=1;
			for(int i=1;i<=L;++i) {
				for(int j=1;j<=Math.min(N, i);++j) {
					dp[i][j] = dp[i-1][j-1]*(N-j+1);
	                dp[i][j] %= MOD;
	                dp[i][j] += dp[i-1][j]*Math.max(0, j-K);
	                dp[i][j] %= MOD;
				}
			}
			return (int) dp[L][N];
    }
}
